package Test;

import java.text.NumberFormat;

public class LevenshteinAlgorithm {
    public static void main(String[] args) {
        // 要⽐较的两个字符串
        String[] str1 = {"亲爱的朋友们，⼤家早上好.", "abcdef"};
        String[] str2 = {"亲爱的朋友们，⼤家完上好.", "abcdefg"};
        for (int i = 0; i < str1.length; i++) {
            levenshtein(str1[i], str2[i]);
        }
    }

    /**
     * 分析　　拼字检查　　语⾳辨识　　抄袭侦测
     * DNA
     */
    public static void levenshtein(String str, String tkRangeName) {

// 计算两个字符串的长度。
        int source = str.length();
        int target = tkRangeName.length();

// 建⽴上⾯说的数组，⽐字符长度⼤⼀个空间
        int[][] dif = new int[source + 1][target + 1];


//    赋初值，步骤    B。

        for (int a = 0; a <= source; a++) {
            dif[a][0] = a;
        }
        for (int a = 0; a <= target; a++) {
            dif[0][a] = a;
        }

//计算两个字符是否⼀样，计算左上的值
        int temp;
        for (int i = 1; i <= source; i++) {
            for (int j = 1; j <= target; j++) {
                if (str.charAt(i - 1) == tkRangeName.charAt(j - 1)) {
                    temp = 0;
                } else {
                    temp = 1;
                }
// 取三个值中最⼩的
                dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1, dif[i - 1][j] + 1);
            }
        }
        System.out.println("字符串\"" + str + "\"与\"" + tkRangeName + "\"的⽐较");

//   取数组右下⾓的值，同样不同位置代表不同字符串的⽐较
        System.out.println("差异步骤：" + dif[source][target]);

// 计算相似度
        float similarity = 1 - (float) dif[source][target] / Math.max(str.length(), tkRangeName.length());
        System.out.println("相似度：" + getPercentValue(similarity));
    }

    public static String getPercentValue(float similarity) {
        NumberFormat fmt = NumberFormat.getPercentInstance();
        // 最多两位百分⼩数，如      25.23%
        fmt.setMaximumFractionDigits(2);

        return fmt.format(similarity);
    }

    // 得到最⼩值
    private static int min(int... is) {
        int min = Integer.MAX_VALUE;
        for (int i : is) {
            if (min > i) {
                min = i;
            }
        }
        return min;
    }
}

